package no83;

import java.util.HashMap;
import java.util.Map;

/**
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
 *
 * 返回同样按升序排列的结果链表。
 *
 *
 * 示例 1：
 * 输入：head = [1,1,2]
 * 输出：[1,2]
 * 示例 2：
 * 输入：head = [1,1,2,3,3]
 * 输出：[1,2,3]
 *  
 *
 *
 * @author wangjie
 * @version V1.0
 * @date 2021/3/26
 */
public class Solution {

    /**
     * 我的解法，想复杂了
     * @param head
     * @return
     */
    public ListNode deleteDuplicates(ListNode head) {

        ListNode tem = head;
        if(null != head){
            Map<Integer,ListNode> map = new HashMap();
            map.put(head.val,head);

            while(null != head.next){
                if(map.containsKey(head.next.val)){
                    head.next = head.next.next;
                }else{
                    map.put(head.next.val,head.next);
                    head = head.next;
                }
            }
        }
        return tem;
    }

    /**
     * 优解
     * @param head
     * @return
     */
    public ListNode deleteDuplicatesNew(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null) {
            if(cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }


    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
